/**
 * [63] 不同路径 II
 *
 * @format
 * @lc app=leetcode.cn id=63 lang=javascript
 */

// @lc code=start
/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
// 动态规划
var uniquePathsWithObstacles = function (obstacleGrid) {
    const [M, N] = [obstacleGrid.length, obstacleGrid[0].length]
    // if (obstacleGrid[M - 1][N - 1] == 1) return 0
    // 初始化备忘录：边缘为 1（障碍后为 0），障碍为 0，未知为 null
    let flags = [false, false]
    const paths = []
    for (let i = M - 1; i >= 0; i--) {
        paths.push([])
        for (let j = N - 1; j >= 0; j--) {
            let [x, y] = [N - j - 1, M - i - 1]
            if (obstacleGrid[i][j] == 1) {
                paths[y].push(0)
                if (i == M - 1) flags[0] = true
                if (j == N - 1) flags[1] = true
            } else if (i == M - 1) {
                flags[0] ? paths[0].push(0) : paths[0].push(1)
            } else if (j == N - 1) {
                flags[1] ? paths[y].push(0) : paths[y].push(1)
            } else paths[M - i - 1].push(paths[y - 1][x] + paths[y][x - 1])
        }
    }
    // 待求网格索引（降维减少循环层数）：(M - 1)(N - 1) - 1
    // let index = N + 1
    // while (index < M * N) {
    //     let [i, j] = [Math.floor(index / N), index % N]
    //     if (paths[i][j] == null) paths[i][j] = paths[i - 1][j] + paths[i][j - 1]
    //     index++
    // }
    return paths[M - 1][N - 1]
}
// 递归
// var uniquePathsWithObstacles = function (obstacleGrid) {
//     if (obstacleGrid[0][0]) return 0
//     function waysToEnd(x, y, grid) {
//         if (y == grid.length - 1 && x == grid[0].length - 1) {
//             return grid[y][x] ? 0 : 1
//         }
//         let count = 0
//         if (y + 1 < grid.length && !grid[y + 1][x]) {
//             count += waysToEnd(x, y + 1, grid)
//         }
//         if (x + 1 < grid[0].length && !grid[y][x + 1]) {
//             count += waysToEnd(x + 1, y, grid)
//         }
//         return count
//     }
//     return waysToEnd(0, 0, obstacleGrid)
// }
// var uniquePathsWithObstacles = function (obstacleGrid) {
//     function uniquePaths(m, n) {
//         const DOWN = n - 1
//         const RIGHT = m - 1
//         const TOTAL = m + n - 2
//         if (TOTAL == -2) return 0
//         let [total_f, right_f, down_f] = [1, 1, 1]
//         for (let i = 1; i <= TOTAL; i++) {
//             total_f *= i
//             if (i == DOWN) down_f = total_f
//             if (i == RIGHT) right_f = total_f
//         }
//         return total_f / (right_f * down_f)
//     }
//     const [TOTAL_M, TOTAL_N] = [obstacleGrid.length, obstacleGrid[0].length]
//     let [i, j] = [0, 0]
//     while (i < TOTAL_M) {
//         j = 0
//         while (j < TOTAL_N) {
//             if (obstacleGrid[i][j]) break
//             j++
//         }
//         if (obstacleGrid[i][j]) break
//         i++
//     }
//     const [OBSTACLE_M, OBSTACLE_N, END_M, END_N] = [
//         i + 1,
//         j + 1,
//         TOTAL_M - i,
//         TOTAL_N - j
//     ]
//     return (
//         uniquePaths(TOTAL_M, TOTAL_N) -
//         uniquePaths(OBSTACLE_M, OBSTACLE_N) * uniquePaths(END_M, END_N)
//     )
// }
// debugger
// const obstacleGrid = [
//     [0, 0, 0],
//     [0, 1, 0],
//     [0, 0, 0]
// ]
// const WAYS = uniquePathsWithObstacles(obstacleGrid)
// console.log(WAYS)
// @lc code=end
